package com.xypower.tree;

import java.util.HashMap;
import java.util.HashSet;

//最低公共祖先
public class LowestCommonAncestor {
    public static class Node{
        public int value;
        public Node left;
        public Node right;

        public Node(int data) {
            this.value = data;
        }
    }

    public static Node lowestAncestor(Node head,Node o1,Node o2){
        if (head == null || head == o1 || head == o2){//base case
            return head;
        }
        Node left = lowestAncestor(head.left,o1,o2);
        Node rig1ht = lowestAncestor(head.right,o1,o2);
        if (left != null && rig1ht != null){
            return head;
        }

        return left != null ? left : rig1ht;
    }

    //o1、o2一定属于head为头的树，返回o1和o2的公共祖先
//    public static Node lca(Node head,Node o1,Node o2){
//        HashMap<Node,Node> fatherMap = new HashMap<>();
//        fatherMap.put(head,head);
//        process(head,fatherMap);
//        HashSet<Node> set1 = new HashSet<>();
//
//        Node cur = o1;
//        while (cur != fatherMap.get(cur)){
//            set1.add(o1);
//            cur = fatherMap.get(cur);
//        }
//        set1.add(head);
//
//        //判断o2在不在set里，在的话则为最低公共祖先
//    }
//
//
//    public static void process(Node head, HashMap<Node,Node> fatherMap){
//        if (head == null){
//            return;
//        }
//        fatherMap.put(head.left,head);
//        fatherMap.put(head.right,head);
//        process(head.left,fatherMap);
//        process(head.right,fatherMap);
//    }
}
